/***尚硅谷Java数据结构与java算法                  ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***克鲁斯卡尔算法        P174                   ***/
/***C++ 实现版本    written by Daniel           ***/
#include <vector>
#include <iostream>
#include <algorithm>

typedef struct eData
{
    char start;
    char end;
    int weight;
    eData() = delete;
    eData(char start, char end, int weight) : start(start), end(end), weight(weight){};
    //重载<，用于排序
    bool operator<(const eData &data)
    {
        return this->weight < data.weight ? true : false;
    }
} eData;
//图类
class mGraph
{
public:
    mGraph() = delete;
    mGraph(int num, std::vector<char> vertexVec, std::vector<std::vector<int>> weightVec) : vertexNum(num), vertexVec(vertexVec), weightVec(weightVec)
    {
        //生成dataVec，用于给距离排序
        for (int i = 0; i < vertexNum; i++)
        {
            for (int j = i + 1; j < vertexNum; j++)
            {
                if (weightVec[i][j] != 10000)
                {
                    dataVec.push_back(eData(vertexVec[i], vertexVec[j], weightVec[i][j]));
                }
            }
        }
        //直接排序
        std::sort(dataVec.begin(), dataVec.end());
    }
    mGraph(mGraph &graph) = default;
    mGraph(mGraph &&graph) = default;
    /*
    功能：使用普利姆算法，建造一个最小生成树
    参数：start  开始的位置，即第几个节点，从零开始
    返回值： 空
    */
    void prim(int start)
    {
        //0代表没有访问过
        std::vector<bool> isVisited(vertexNum, false);
        isVisited[start] = true;
        int tempFrom = -1;
        int tempTo = -1;
        std::vector<std::pair<int, int>> path;
        //从已经访问过的节点中，找到最小距离最小的节点
        for (int k = 1; k < vertexNum; k++)
        {
            int weightMin = 10000;
            for (int i = 0; i < vertexNum; i++)
            {
                if (isVisited[i])
                {
                    for (int j = 0; j < vertexNum; j++)
                    {
                        if ((!isVisited[j]) && weightVec[i][j] < weightMin)
                        {
                            weightMin = weightVec[i][j];
                            tempFrom = i;
                            tempTo = j;
                        }
                    }
                }
            }
            path.push_back(std::make_pair(tempFrom, tempTo));
            isVisited[tempTo] = true;
        }
        int totalPath = 0;
        for (const auto &item : path)
        {
            totalPath += weightVec[item.first][item.second];
            std::cout << vertexVec[item.first] << ">>" << vertexVec[item.second] << "\t路径长度" << weightVec[item.first][item.second] << std::endl;
        }
        std::cout << "路径总长度" << totalPath << std::endl;
    }
    /*
    功能：克鲁斯卡尔算法,从n个顶点中依次选择n-1条，并且不构成回路的边
    参数：void 空
    返回值:void 空
    */
    void kruskal()
    {
        //用于放结果的容器
        std::vector<eData> resData;
        resData.reserve(vertexNum - 1);
        std::vector<int> ends(vertexNum, 0);
        auto count = dataVec.size();
        for (size_t i = 0; i < count; i++)
        {
            //得到下标
            int p1 = getIndex(dataVec[i].start);
            int p2 = getIndex(dataVec[i].end);
            //此时如果ends[p1]==0,返回值为4  如果为0，认为自己是自己的终点
            int m = getEnd(ends, p1);
            int n = getEnd(ends, p2);
            //判断两个节点是否为同一终点，如不是，加入结果vector
            if (m != n)
            {
                //把m的终点设置为n，如果前面ends[p1]和ends[p2]均为0，则会把p1的终点变为n
                ends[m] = n;
                resData.push_back(dataVec[i]);
            }
            //若是同一个节点，退出当前循环，进行下一个循环
        }
        printDataVec(resData);
    }
    int getIndex(char pos)
    {
        for (int i = 0; i < vertexNum; i++)
        {
            if (pos == vertexVec[i])
            {
                return i;
            }
        }
        return -1;
    }

    //得到节点的终点
    int getEnd(std::vector<int> &ends, int i)
    {
        //有点难懂
        while (ends[i] != 0)
        {
            i = ends[i];
        }
        return i;
    }

    void printWeight()
    {
        for (const auto &item : weightVec)
        {
            for (const auto &item1 : item)
            {
                std::cout << item1 << "\t";
            }
            std::cout << std::endl;
        }
    }
    void printDataVec(const std::vector<eData> &dataVec)
    {
        for (const auto &item : dataVec)
        {
            std::cout << "start:" << item.start << "\t"
                      << "end:" << item.end << "\t"
                      << "weight:" << item.weight << std::endl;
        }
    }

private:
    int vertexNum;
    std::vector<char> vertexVec;
    std::vector<std::vector<int>> weightVec;
    std::vector<eData> dataVec;
};

//测试代码
int main()
{
    int vertexNum = 7;
    std::vector<char> vertexVec({'A', 'B', 'C', 'D', 'E', 'F', 'G'});
    int arr[vertexNum][vertexNum] =
        {{10000, 12, 10000, 10000, 10000, 16, 14},
         {12, 10000, 10, 10000, 10000, 7, 10000},
         {10000, 10, 10000, 3, 5, 6, 10000},
         {10000, 10000, 3, 10000, 4, 10000, 10000},
         {10000, 10000, 5, 4, 10000, 2, 8},
         {16, 7, 6, 10000, 2, 10000, 9},
         {14, 10000, 10000, 10000, 8, 9, 10000}};
    std::vector<std::vector<int>> weightVec(vertexNum, std::vector<int>(vertexNum, 0));
    for (int i = 0; i < vertexNum; i++)
    {
        for (int j = 0; j < vertexNum; j++)
        {
            weightVec[i][j] = arr[i][j];
        }
    }
    mGraph *graph = new mGraph(vertexNum, vertexVec, weightVec);
    graph->printWeight();
    graph->prim(2);
    std::cout << "kruskal way:" << std::endl;
    graph->kruskal();
    if (graph != nullptr)
    {
        delete graph;
        graph = nullptr;
    }
}